package simple;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/5/4 20:29
 */
public class No70_爬楼梯 {
    public static void main(String[] args) {
        Solution70 solution70 = new Solution70();
        //不考虑溢出问题,不是本题研究方向
        for (int i = 1; i <= 45; i++) {
            System.out.println(solution70.climbStairs(i));
        }
    }
}

class Solution70 {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        //矩阵法
        int[][] base = new int[2][2];
        getBase(base, n - 1);
        int f0 = 1;
        int f1 = 1;
        return base[0][0] * f1 + base[0][1] * f0;
    }

    //获取 1 1
    //     1 0 n 次方
    public void getBase(int[][] base, int n) {
        //初始化
        base[0][0] = 1;
        base[0][1] = 1;
        base[1][0] = 1;
        base[1][1] = 0;
        int tmp00 = 1;
        int tmp01 = 1;
        int tmp10 = 1;
        int tmp11 = 0;
        //第二次开始循环
        for (int i = 2; i <= n; i++) {
            int base00 = base[0][0] * tmp00 + base[0][1] * tmp10;
            int base01 = base[0][0] * tmp01 + base[0][1] * tmp11;
            int base10 = base[1][0] * tmp00 + base[1][1] * tmp10;
            int base11 = base[1][0] * tmp01 + base[1][1] * tmp11;
            base[0][0] = base00;
            base[0][1] = base01;
            base[1][0] = base10;
            base[1][1] = base11;
        }
    }
}
    //public int climbStairs(int n) {
    //    //1 1 2 3 5
    //    //斐波那契数列,通项公式,直接套用
    //    //获取根号5
    //    double g5 = Math.sqrt(5.0);
    //    double a = Math.pow((1 + g5) / 2, n + 1);
    //    double b = Math.pow((1 - g5) / 2, n + 1);
    //
    //    double result = 1 / g5 * (a - b);
    //    return (int) result;
    //}


    //public int climbStairs(int n) {
    //    //动态规划
    //    int[] dp = new int[n + 66];//随便
    //    dp[1] = 1;
    //    dp[2] = 2;
    //    for (int i = 3; i <= n; i++) {
    //        dp[i] = dp[i - 1] + dp[i - 2];
    //    }
    //    return dp[n];
    //}



    //public int climbStairs(int n) {
    //    //暴力法
    //    int[] ji = new int[n + 10];//随便什么都可以
    //    return climbStairs(0, n, ji);
    //}
    //
    ////current:当前位置,n:台阶总数
    //public int climbStairs(int current, int n,int[] ji) {
    //    if (ji[current] > 0) {
    //        return ji[current];
    //    }
    //    //递归结束条件
    //    if (n - current <= 2) {
    //        ji[current] = n - current;
    //    } else {
    //        ji[current] = climbStairs(current + 1, n, ji) + climbStairs(current + 2, n, ji);
    //    }
    //    return ji[current];
    //}

    //public int climbStairs(int n) {
    //    //暴力法
    //    return climbStairs(0, n);
    //}
    //
    ////current:当前位置,n:台阶总数
    //public int climbStairs(int current, int n) {
    //    //递归结束条件
    //    if (n - current <= 2) {
    //        return n - current;
    //    } else {
    //        return climbStairs(current + 1, n) + climbStairs(current + 2, n);
    //    }
    //}